package Java道题;

import java.util.Scanner;

public class 求斐波那契数矩阵 {
    /*
     * ①　a是double类型，求a^n
       ②　斐波那契数列{1，1，2，3，5，8，13}
        {算法 1：递归 O((1+sqrt(5))^n)
         算法 2：循环迭代 O(n)
         算法3：令矩阵 A={1,1,1,0} 则A^n={Fn+1,Fn,Fn,Fn-1}.O(lg(n))
     */
    static	public class M
    {
        public int m11,m12,m21,m22;
        M(int m11,int m12,int m21,int m22)
        {
            this.m11=m11;
            this.m12=m12;
            this.m21=m21;
            this.m22=m22;
        }

    }
    public static int fib(int n)
    {
        M m = new M(1,1,1,0);

        M result=An(m,n);
        return result.m21;

    }
    private static M An(M m, int n) {
        // TODO Auto-generated method stub
        M result;
        if(n==1)
        {
            return m;
        }
        if(n%2==0)
        {
            result=An(m,n/2);
            return mulM(result,result);

        }
        else
        {
            return mulM(m,An(m,n-1));
        }
    }
    private static M mulM(M m1, M m2) {
        // TODO Auto-generated method stub
        M m = new M(0,0,0,0);
        m.m11=m1.m11*m2.m11+m1.m12*m2.m21;
        m.m12=m1.m11*m2.m12+m1.m12*m2.m22;
        m.m21=m1.m21*m2.m11+m1.m22*m2.m21;
        m.m22=m1.m21*m2.m12+m1.m22*m2.m22;

        return m;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner ss=new Scanner(System.in);

        int n=ss.nextInt();
        int i=1;
        while(i<=n)
        {
            System.out.print(fib(i
            )+" ");//1,1,2,3,5,8,13
            i++;
        }
    }

}
